package com.ankie.algorithm;

import java.util.Arrays;

/**
 * @ClassName HeapSort
 * @Author ankie
 * @Date 2020/6/10
 * @Description 堆排序，条件利用完全二叉树
 */
public class HeapSort {

    private static void swap(int[] tree, int i, int j) {
        int temp = tree[i];
        tree[i] = tree[j];
        tree[j] = temp;
    }

    // 构建小二叉树中的大顶堆，
    // 其中 n 存在的意义，在于排序阶段不断的缩小需要最大值和最小值交换的范围
    private static void heapify(int[] tree, int n, int i) {
        if (i >= n) {
            // 递归的返回条件
            return;
        }
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        int max = i;
        // 需要同时确保 left 和 right 不出界
        if (left < n && tree[left] > tree[max]) {
            max = left;
        }
        if (right < n && tree[right] > tree[max]) {
            max = right;
        }
        if (max != i) {
            swap(tree, max, i);
            heapify(tree, n, max);
        }
    }

    // 构建一个大顶堆
    private static void buildHeap(int[] tree) {
        // 这是堆中最后一个节点的索引
        int lastNode = tree.length - 1;
        // 这是最后一个节点构成的小二叉树的父节点
        int parent = (lastNode - 1) / 2;
        // 从倒数第一层，开始构建大顶堆，这里是从下到上构建大顶堆
        for (int i = parent; i >= 0; i--) {
            heapify(tree, tree.length, i);
        }
    }

    // 构建大顶堆后，交换最大值和最小值，重新构建大顶堆，然后逐渐缩小范围
    private static void heapSort(int[] tree) {
        buildHeap(tree);

        for (int i = tree.length - 1; i >= 0; i--) {
            swap(tree, i, 0);
            // 这里树是不断减少的，缩减的范围就是由 i 来决定的
            heapify(tree, i, 0);
        }
    }

    public static void main(String[] args) {
        int[] arr = {3, 44, 38, 5, 47, 15, 36, 26, 66, 29, 50, 48, 27};
        System.out.println(Arrays.toString(arr));
        heapSort(arr);
        System.out.println(Arrays.toString(arr));
    }
}
